package com.yuan.algorithms.base01;

import java.util.Scanner;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年10月13日 下午3:36:02
 * <br>说明:
 */
public class 递归_全排列 {

	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		while(in.hasNext()) {
			String str = in.next();
			permute(str);
		}
	}
	private static void permute(String str) {
		char[] data = str.toCharArray();
		premute(data, 0, data.length);
	}
	
	/**
	 * 递归交换元素位置求全排列
	 * @param data 数据数组
	 * @param low 当前位置
	 * @param high 最高位（元素长度）
	 */
	private static void premute(char[] data, int low, int high) {
		if (low == high) {
			for(char k : data) {
				System.out.print(k);
			}
			System.out.println();
			return;
		}
		for (int i = low; i < high; i++) {
			{
				//交换元素位置
				char temp = data[i];
				data[i] = data[low];
				data[low] = temp;
			}
			premute(data, low+1, high);
			{
				//回溯
				char temp = data[i];
				data[i] = data[low];
				data[low] = temp;
			}
		}
		
	}

}
